{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Moves in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxMoves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中移动的最大次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、大小为 <code>m x n</code> 的矩阵 <code>grid</code> ，矩阵由若干 <strong>正</strong> 整数组成。</p>\n",
    "\n",
    "<p>你可以从矩阵第一列中的 <strong>任一</strong> 单元格出发，按以下方式遍历&nbsp;<code>grid</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从单元格 <code>(row, col)</code> 可以移动到&nbsp;<code>(row - 1, col + 1)</code>、<code>(row, col + 1)</code> 和 <code>(row + 1, col + 1)</code> 三个单元格中任一满足值 <strong>严格</strong> 大于当前单元格的单元格。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回你在矩阵中能够 <strong>移动</strong> 的 <strong>最大</strong> 次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/11/yetgriddrawio-10.png\" style=\"width: 201px; height: 201px;\">\n",
    "<pre><strong>输入：</strong>grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>可以从单元格 (0, 0) 开始并且按下面的路径移动：\n",
    "- (0, 0) -&gt; (0, 1).\n",
    "- (0, 1) -&gt; (1, 2).\n",
    "- (1, 2) -&gt; (2, 3).\n",
    "可以证明这是能够移动的最大次数。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/12/yetgrid4drawio.png\">\n",
    "<strong>输入：</strong>grid = [[3,2,4],[2,1,9],[1,1,7]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>从第一列的任一单元格开始都无法移动。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>2 &lt;= m, n &lt;= 1000</code></li>\n",
    "\t<li><code>4 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-moves-in-a-grid](https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-moves-in-a-grid](https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]', '[[3,2,4],[2,1,9],[1,1,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, a: List[List[int]]) -> int:\n",
    "        n,m = len(a), len(a[0])\n",
    "        dp = [[0] * m for i in range(n)]\n",
    "        ans = 0\n",
    "        for j in range(m-2, -1, -1):\n",
    "            for i in range(n):\n",
    "                for di in range(-1,2):\n",
    "                    ii = i + di\n",
    "                    if ii < 0 or ii >= n:\n",
    "                        continue\n",
    "                    if a[i][j] < a[ii][j + 1]:\n",
    "                        dp[i][j] = max(dp[i][j], dp[ii][j + 1] + 1)\n",
    "                if j == 0:\n",
    "                    ans = max(ans, dp[i][j])\n",
    "        return ans                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [0] * m\n",
    "        ans = 0\n",
    "        for j in range(1, n):\n",
    "            tdp = [0] * m\n",
    "            for i in range(m):\n",
    "                if i-1>=0 and dp[i-1]==j-1 and grid[i][j] > grid[i-1][j-1]:\n",
    "                    tdp[i] = j\n",
    "                elif dp[i]==j-1 and grid[i][j] > grid[i][j-1]:\n",
    "                    tdp[i] = j\n",
    "                elif i+1<m and dp[i+1]==j-1 and grid[i][j] > grid[i+1][j-1]:\n",
    "                    tdp[i] = j\n",
    "                else:\n",
    "                    tdp[i] = 0\n",
    "            mx = max(tdp)\n",
    "            if mx == 0:\n",
    "                break\n",
    "            dp = tdp\n",
    "            ans = mx\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [0] * m\n",
    "\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            c = dp.copy()\n",
    "            for i in range(m):\n",
    "                dp[i] = 0\n",
    "                for k in range(max(i - 1, 0), min(i + 2, m)):\n",
    "                    if grid[i][j] < grid[k][j + 1]:\n",
    "                        dp[i] = max(dp[i], c[k] + 1)\n",
    "            \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        s=set(range(m))\n",
    "        for j in range(1,n):\n",
    "            ss=set()\n",
    "            for i in range(m):\n",
    "                if i-1>=0:\n",
    "                    if grid[i][j]>grid[i-1][j-1] and i-1 in s:\n",
    "                        ss.add(i)\n",
    "                if grid[i][j]>grid[i][j-1] and i in s:\n",
    "                    ss.add(i)\n",
    "                if i+1<m:\n",
    "                    if grid[i][j]>grid[i+1][j-1] and i+1 in s:\n",
    "                        ss.add(i)\n",
    "            if len(ss)==0:\n",
    "                return j-1\n",
    "            s=ss \n",
    "        return n-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        for j in range(m):\n",
    "            vis[j][0] = True\n",
    "            q.append((j, 0))\n",
    "        while q:\n",
    "            x, y = q.pop()\n",
    "            # ans = max(ans, y)\n",
    "            for nx, ny in zip((x-1, x, x+1),(y+1, y+1, y+1)):\n",
    "                if 0<=nx<len(grid) and 0<=ny<len(grid[0]) and grid[nx][ny]>grid[x][y] and not vis[nx][ny]:\n",
    "                    vis[nx][ny] = True\n",
    "                    q.appendleft((nx,ny))\n",
    "                    ans = max(ans, ny)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        tmp = [[0] * len(grid[0]) for _ in range(len(grid))]\n",
    "        ans = 0\n",
    "        for i in range(len(grid[0]) - 2, -1, -1):\n",
    "            for j in range(len(grid)):\n",
    "                tmp[j][i] = max(tmp[j][i],\n",
    "                                tmp[j][i + 1] + 1 if grid[j][i + 1] > grid[j][i] else 0,\n",
    "                                tmp[j + 1][i + 1] + 1 if j + 1 < len(grid) and grid[j + 1][i + 1] > grid[j][i] else 0,\n",
    "                                tmp[j - 1][i + 1] + 1 if j - 1 >= 0 and grid[j - 1][i + 1] > grid[j][i] else 0)\n",
    "        for n in range(len(grid)):\n",
    "            ans = max(ans, tmp[n][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            for i in range(m):\n",
    "                for k in range(max(i - 1, 0), min(i + 2, m)):\n",
    "                    if grid[i][j] < grid[k][j + 1]:\n",
    "                        dp[i][j] = max(dp[i][j], dp[k][j + 1] + 1)\n",
    "        \n",
    "        return max(dp[i][0] for i in range(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def backtrace(dp, m, n, grid, i, j, value):\n",
    "    if i < 0 or j < 0 or i > m -1 or j > n - 1:\n",
    "        return 0\n",
    "    if dp[i][j] == 1:\n",
    "        return 0\n",
    "    \n",
    "    if grid[i][j] <= value:\n",
    "        return 0\n",
    "    dp[i][j] = 1\n",
    "    mx1 = max(backtrace(dp, m, n, grid, i - 1, j + 1, grid[i][j]), backtrace(dp, m, n, grid, i, j + 1, grid[i][j]))\n",
    "    mx1 = max(backtrace(dp, m, n, grid, i + 1, j + 1, grid[i][j]), mx1)\n",
    "    return 1 + mx1\n",
    "        \n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        # 定义当坐标为i，j时的搜索策略\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        max2 = 0\n",
    "        for i in range(m):\n",
    "            dp = [[0] * n for i in range(m)]\n",
    "            max2 = max(max2, backtrace(dp, m, n, grid, i, 0, 0))\n",
    "        return max2 - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        grid.append([inf]*m)\n",
    "        grid.insert(0,[inf]*m)\n",
    "        ward = [(1,-1),(0,-1),(-1,-1)]\n",
    "        arr = [[0]+[-inf for _ in range(m-1)] for _ in range(n+2)]\n",
    "        ans = 0\n",
    "        for j in range(1,m):\n",
    "            for i in range(1,n+1):\n",
    "                for x,y in ward:\n",
    "                    if grid[i][j]>grid[i+x][j+y]:\n",
    "                        arr[i][j] = max(arr[i][j],arr[i+x][j+y]+1)\n",
    "                        ans = max(ans,arr[i][j])\n",
    "        return ans\n",
    "\n",
    "\n",
    "        print(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        def dfs(i, j):\n",
    "            ans = 0\n",
    "            vis[i][j] = 1\n",
    "            for x, y in (i - 1, j + 1), (i, j + 1), (i + 1, j + 1):\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j] and not vis[x][y]:\n",
    "                    ans = max(ans, dfs(x, y) + 1)\n",
    "            return ans\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            vis = [[0] * n for _ in range(m)]\n",
    "            ans = max(ans, dfs(i, 0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        dp = [[0] * m for i in range(n)]\n",
    "\n",
    "        def dfs(row: int, col: int) -> int:\n",
    "            if col == m - 1:\n",
    "                return 0\n",
    "            if dp[row][col] != 0:\n",
    "                return dp[row][col]\n",
    "\n",
    "            for i in range(-1, 2):\n",
    "                r = row + i\n",
    "                if 0 <= r < n and grid[row][col] < grid[r][col + 1]:\n",
    "                    dp[row][col] = max(dp[row][col], dfs(r, col + 1) + 1)\n",
    "\n",
    "            return dp[row][col]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dfs(i, 0))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        count = [0]\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        visit = [[False] * col for _ in range(row)]\n",
    "\n",
    "        def dfs(c, a, b):\n",
    "            visit[a][b] = True\n",
    "            count[0] = max(count[0], c)\n",
    "            if b+1 == col:\n",
    "                return\n",
    "            if a-1 >= 0 and not visit[a-1][b+1] and grid[a-1][b+1] > grid[a][b]:\n",
    "                dfs(c+1, a-1, b+1)\n",
    "            if not visit[a][b+1] and grid[a][b+1] > grid[a][b]:\n",
    "                dfs(c+1, a, b+1)\n",
    "            if a+1 < row and not visit[a+1][b+1] and grid[a+1][b+1] > grid[a][b]:\n",
    "                dfs(c+1, a+1, b+1)\n",
    "        for i in range(row):\n",
    "            dfs(0, i, 0)\n",
    "            if count[0] == col-1:\n",
    "                break\n",
    "        return count[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        def dfs(i, j):\n",
    "            for dx, dy in [(-1,1),(0,1),(1,1)]:\n",
    "                newx = i+dx\n",
    "                newy = j+dy\n",
    "                if 0 <= newx < m and 0 <= newy < n and grid[i][j] < grid[newx][newy]:\n",
    "                    if ans[newx][newy] == 0:\n",
    "                        dfs(newx, newy)\n",
    "                    ans[i][j] = max(ans[i][j], ans[newx][newy]+1)\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            dfs(i, 0)\n",
    "        return max(max(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        height = len(grid)\n",
    "        width = len(grid[0])\n",
    "\n",
    "        memory = [[-1 for _ in range(width)] for _ in range(height)]\n",
    "\n",
    "        def find_max_step(row: int, col: int, current_step: int) -> int:\n",
    "            if not (0 <= row < height and 0 <= col < width):\n",
    "                return current_step - 1\n",
    "\n",
    "            if memory[row][col] == -1:\n",
    "                memory[row][col] = current_step\n",
    "                for next_row, next_col in [(row - 1, col + 1), (row, col + 1), (row + 1, col + 1)]:\n",
    "                    if 0 <= next_row < height and 0 <= next_col < width and grid[next_row][next_col] > grid[row][col]:\n",
    "                        step = find_max_step(next_row, next_col, current_step + 1)\n",
    "                        memory[row][col] = max(memory[row][col], step)\n",
    "            return memory[row][col]\n",
    "\n",
    "        max_step = 0\n",
    "\n",
    "        for i in range(height):\n",
    "            max_step = max(max_step, find_max_step(i, 0, 0))\n",
    "        return max_step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "    \n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        \n",
    "        move_map = [[0 for i in range(col)] for j in range(row)]\n",
    "                           \n",
    "        def val(x, y, next_x, next_y):\n",
    "            if next_x >= 0 and next_x < row and next_y >= 0 and next_y < col and \\\n",
    "                grid[next_x][next_y] > grid[x][y]:\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        ans = 0\n",
    "        path = 0\n",
    "        def dfs(x, y):\n",
    "            nonlocal ans\n",
    "            nonlocal path\n",
    "            nonlocal move_map\n",
    "            if x >= row or y >= col:\n",
    "                if path > ans:\n",
    "                    ans = path\n",
    "                return \n",
    "            \n",
    "            if move_map[x][y]:\n",
    "                return\n",
    "            \n",
    "            move_map[x][y] = 1\n",
    "            for (nx, ny) in [(x-1, y+1), (x, y+1), (x+1,y+1)]:\n",
    "                if val(x, y, nx, ny):\n",
    "                    path += 1\n",
    "                    dfs(nx, ny)\n",
    "                    path -= 1\n",
    "                    \n",
    "            if path > ans:\n",
    "                ans = path\n",
    "        \n",
    "        for j in range(0, row):\n",
    "                # j, 0\n",
    "            dfs(j, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        max_step = [ [True for _ in range(len(grid[0]))] for _ in  range(len(grid)) ]\n",
    "        max_list = []\n",
    "        def dfs(i,j):\n",
    "            if j == len(grid[0])-1:\n",
    "                max_list.append(j)\n",
    "                return\n",
    "            for i_plus in range(-1,2):\n",
    "                if i+i_plus > -1 and i+i_plus < len(grid):\n",
    "                    if grid[i+i_plus][j+1] > grid[i][j] and max_step[i+i_plus][j+1]:\n",
    "                        dfs(i+i_plus,j+1)\n",
    "            max_step[i][j] = False\n",
    "            max_list.append(j)\n",
    "            return\n",
    "        for k in range(len(grid)):\n",
    "            dfs(k,0)\n",
    "        return max(max_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        #f = [[-1] * m] * n 每行之间共享数据单元\n",
    "        f = [[-1 for i in range(m)] for i in range(n)]\n",
    "        #print(f)\n",
    "        dx = [-1, 0, 1]\n",
    "        dy = [1, 1, 1]\n",
    "\n",
    "        def dp(x, y):\n",
    "            #print(x, y, f[x][y])\n",
    "            if f[x][y] != -1:\n",
    "                return f[x][y]\n",
    "            f[x][y] = 0\n",
    "            #print(x, y, f[x][y])\n",
    "            for i in range(3):\n",
    "                a, b = x + dx[i], y + dy[i]\n",
    "                #print(a, b, grid[a][b])\n",
    "                if a >= 0 and a < n and b >= 0 and b < m and grid[a][b] > grid[x][y]:\n",
    "                    f[x][y] = max(dp(a, b) + 1, f[x][y])\n",
    "                    \n",
    "                    #print(a, b, f[a][b])\n",
    "            #print(x, y, f[x][y])\n",
    "            #print(f[1][0])\n",
    "            return f[x][y]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            #print(i)\n",
    "            #print(f[1][0])\n",
    "            res = max(res, dp(i, 0))\n",
    "        #print(f)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        def deepSearch(i, j):\n",
    "            if arr[i][j] != -1: return arr[i][j]\n",
    "            pos = [[-1, 1], [0, 1], [1, 1]]\n",
    "            ans = -1\n",
    "            for x, y in pos:\n",
    "                x += i\n",
    "                y += j\n",
    "                if 0 <= x < m and 0 <= y < n and grid[i][j] < grid[x][y]:\n",
    "                    if arr[x][y] == -1:\n",
    "                        arr[x][y] = deepSearch(x, y)\n",
    "                    ans = max(ans, arr[x][y])\n",
    "            arr[i][j] = 0 if ans == -1 else ans + 1\n",
    "            return arr[i][j]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        arr = [[-1] * n for _ in range(m)]\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            res = max(res, deepSearch(i, 0))\n",
    "            # print(arr)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        vis = [[0]*n for _ in range(m)]\n",
    "        ret = [[0]*n for _ in range(m)]\n",
    "        ds = [\n",
    "            [-1, 1],\n",
    "            [0, 1],\n",
    "            [1, 1],\n",
    "        ]\n",
    "        def dfs(i, j):\n",
    "            if vis[i][j]:\n",
    "                return ret[i][j]\n",
    "            r = 0\n",
    "            for d in ds:\n",
    "                ii, jj = i+d[0], j+d[1]\n",
    "                if ii >= 0 and jj >=0 and ii < m and jj < n:\n",
    "                    if grid[ii][jj]> grid[i][j]:\n",
    "                        r = max(r, 1+dfs(ii, jj))\n",
    "            vis[i][j] = 1\n",
    "            ret[i][j] = r\n",
    "            return r\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ret[i][j] = dfs(i, j)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            ans = max(ans, ret[i][0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        vist = [[0] * len(grid[0]) for _ in range(len(grid))]\n",
    "        \n",
    "        def dfs(x,y,v):\n",
    "            if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):\n",
    "                return 0\n",
    "            if grid[x][y] <= v:\n",
    "                return 0\n",
    "            if vist[x][y] == 1:\n",
    "                return 0\n",
    "            else:\n",
    "                vist[x][y] = 1\n",
    "            r = 0\n",
    "            for a,b in (x-1,y+1), (x,y+1), (x+1,y+1):\n",
    "                r = max(r, dfs(a,b,grid[x][y]))\n",
    "            return r + 1\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            res = max(res, dfs(i,0,0))\n",
    "        return res - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        dir = [[-1, 1], [0, 1], [1, 1]]\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        f = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            if f[x][y] != -1: return f[x][y]\n",
    "            f[x][y] = 0\n",
    "            for i in range(3):\n",
    "                tx, ty = x + dir[i][0], y + dir[i][1]\n",
    "                if tx <= 0 or tx > n or ty <= 0 or ty > m or grid[tx - 1][ty - 1] <= grid[x - 1][y - 1]: \n",
    "                    continue\n",
    "                f[x][y] = max(f[x][y], dfs(tx, ty) + 1)\n",
    "            return f[x][y]\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            # if f[i][0] == 0:\n",
    "            ans = max(ans, dfs(i, 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dir = [[-1, 1], [0, 1], [1, 1]]\n",
    "        def dfs(path, x, y):\n",
    "            if visited[x][y]:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            visited[x][y] = 1\n",
    "            ans = max(ans, path)\n",
    "            for i, j in dir:\n",
    "                if 0 <= x + i < m and 0 <= y + j < n and grid[x + i][y + j] > grid[x][y]:\n",
    "                    # print(x, y, x + i, y + j)\n",
    "                    dfs(path + 1, x + i, y + j)\n",
    "            \n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            dfs(0, i, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        vis = set()\n",
    "        for i in range(m):\n",
    "            q = [(i, 0)]\n",
    "            vis.add((i,0))\n",
    "            step = 0\n",
    "            while q:\n",
    "                ans = max(ans, step)\n",
    "                tmp = q\n",
    "                q = []\n",
    "                for x, y in tmp:\n",
    "                    for nx, ny in (x - 1, y + 1), (x, y + 1), (x + 1, y + 1):\n",
    "                        if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in vis and grid[nx][ny] > grid[x][y]:\n",
    "                            q.append((nx, ny))\n",
    "                            vis.add((nx, ny))\n",
    "                step += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "\n",
    "\n",
    "        stack=collections.deque()\n",
    "\n",
    "        for i in range(m):\n",
    "            stack.append([i,0,0])\n",
    "        vis=set()\n",
    "        \n",
    "        mx=0\n",
    "        while stack: \n",
    "            x,y,d =stack.popleft()\n",
    "            if (x,y) in vis:\n",
    "                continue\n",
    "            vis.add((x,y))\n",
    "            mx=max(mx,d)\n",
    "            for x1,y1 in [[x-1,y+1],[x,y+1],[x+1,y+1]]:\n",
    "                if 0<=x1<m and 0<=y1<n:\n",
    "                    if grid[x1][y1]>grid[x][y] and (x1,y1) not in vis:\n",
    "                        stack.append([x1,y1,d+1])\n",
    "\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        starts_d = [(0,i,0) for i in range(m)]\n",
    "        starts = [(i,0) for i in range(m)]\n",
    "        q = deque(starts_d)\n",
    "        vis = set(starts)\n",
    "        ans = 0\n",
    "        while q:\n",
    "            d,x,y = q.popleft()\n",
    "            for dx,dy in (x-1,y+1),(x,y+1),(x+1,y+1):\n",
    "                if 0<=dx<m and 0<=dy<n and (dx,dy) not in vis and grid[dx][dy]>grid[x][y]:\n",
    "                    ans = max(ans,d+1)\n",
    "                    q.append((d+1,dx,dy))\n",
    "                    vis.add((dx,dy))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxMoves(self, grid: List[List[int]]) -> int:\n",
    "\t\tres = 0\n",
    "\t\tself.map = {}\n",
    "\t\tfor i in range(len(grid)):\n",
    "\t\t\tres = max(res, self.check(i, 0, grid))\n",
    "\t\treturn res\n",
    "\t\n",
    "\tdef check(self, each: int, col: int, grid: List[List[int]]) -> int:\n",
    "\t\tif col + 1 >= len(grid[0]):\n",
    "\t\t\treturn 0\n",
    "\t\tkey = each * 1001 + col\n",
    "\t\tif key in self.map:\n",
    "\t\t\treturn self.map[key]\n",
    "\t\tcur_val = grid[each][col]\n",
    "\t\tres = 0\n",
    "\t\tif each - 1 >= 0 and grid[each - 1][col + 1] > cur_val:\n",
    "\t\t\tres = 1 + self.check(each - 1, col + 1, grid)\n",
    "\t\tif each + 1 < len(grid) and grid[each + 1][col + 1] > cur_val:\n",
    "\t\t\tres = max(res, 1 + self.check(each + 1, col + 1, grid))\n",
    "\t\tif each >= 0 and grid[each][col + 1] > cur_val:\n",
    "\t\t\tres = max(res, 1 + self.check(each, col + 1, grid))\n",
    "\t\tself.map[key] = res\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        x, y = 0,0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        record = []\n",
    "        temp = set()\n",
    "        for i in range(m):\n",
    "            temp.add((0,i))\n",
    "        record.append(temp)\n",
    "        res = 0\n",
    "        for i in range(1,n):\n",
    "            lastcol = record[i-1]\n",
    "            temp = set()\n",
    "            for pos in lastcol:\n",
    "                y = pos[1]\n",
    "                x = i\n",
    "                for yy in y-1, y, y+1:\n",
    "                    if m > yy >=0 and grid[yy][x] > grid[y][pos[0]]:\n",
    "                         temp.add((x, yy))\n",
    "            if not temp:\n",
    "                break\n",
    "            record.append(temp)\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        du=[-1,0,1]\n",
    "        visited=set()\n",
    "        def dfs(r,c,ans):\n",
    "            visited.add((r,c))\n",
    "            track=[]\n",
    "            for u in du:\n",
    "                a=r+u\n",
    "                b=c+1\n",
    "                if 0<=a<=m-1 and 0<=b<=n-1 and grid[a][b]>grid[r][c] and (a,b) not in visited :\n",
    "                    track.append(dfs(a,b,ans)+1)\n",
    "            if not track:\n",
    "                return 0\n",
    "            return max(track)\n",
    "        res=[]\n",
    "        for i in range(m):\n",
    "            res.append(dfs(i,0,0))\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid),len(grid[0])\n",
    "        dir = [(-1, 1), (0, 1), (1, 1)]\n",
    "        def bfs(sx, sy):\n",
    "            ret = 0\n",
    "            q = deque([(sx, sy, 0)])\n",
    "            vis = {(sx, sy)}\n",
    "            while q:\n",
    "                i, j, step = q.pop()\n",
    "                for dx, dy in dir:\n",
    "                    new_i = i + dx\n",
    "                    new_j = j + dy\n",
    "                    if n > new_j >= 0 <= new_i < m and (new_i, new_j) not in vis and grid[i][j] < grid[new_i][new_j]:\n",
    "                        ret = max(step + 1, ret)\n",
    "                        vis.add((i, j))\n",
    "                        q.append((new_i, new_j, step + 1))\n",
    "            return ret\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            ans = max(ans, bfs(i, 0))\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        vis = {}\n",
    "        q = deque([])\n",
    "        \n",
    "        n,m = len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            q.append([i,0,0])\n",
    "            vis[(i,0)] = 1\n",
    "        re = 0\n",
    "        while q:\n",
    "            i,j,v = q.popleft()\n",
    "            re = max(re, v)\n",
    "            if j < m-1:\n",
    "                if grid[i][j+1] > grid[i][j]:\n",
    "                    if (i,j+1) not in vis:\n",
    "                        vis[(i, j+1)] = 1\n",
    "                        q.append([i, j+1, v+1])\n",
    "#                     flag = True\n",
    "                if i > 0:\n",
    "                    if grid[i-1][j+1] > grid[i][j]:\n",
    "                        vis[(i-1, j+1)] = 1\n",
    "                        q.append([i-1, j+1, v+1])\n",
    "                if i < n-1:\n",
    "                    if grid[i+1][j+1] > grid[i][j]:\n",
    "                        vis[(i+1, j+1)] = 1\n",
    "                        q.append([i+1, j+1, v+1])\n",
    "        \n",
    "#         for j in range(1, m):\n",
    "#             for i in range(n):\n",
    "#                 flag = False\n",
    "#                 if grid[i][j] > grid[i][j-1]:\n",
    "#                     flag = True\n",
    "#                 if i > 0:\n",
    "#                     if grid[i][j] > grid[i-1][j-1]:\n",
    "#                         flag = True\n",
    "#                 if i < n-1:\n",
    "#                     if grid[i][j] > grid[i+1][j-1]:\n",
    "#                         flag = True\n",
    "#                 if not flag:\n",
    "#                     return j-1\n",
    "            \n",
    "        \n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int: \n",
    "        max_step = 0\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            for x, y in (i-1,j+1), (i,j+1), (i+1,j+1):\n",
    "                if 0<=x<row and 0<=y<col and grid[x][y]>grid[i][j]:\n",
    "                    dfs(x,y)\n",
    "                else:\n",
    "                    nonlocal max_step\n",
    "                    max_step = max(max_step, j)\n",
    "                    \n",
    "        for i in range(row):\n",
    "            dfs(i, 0)\n",
    "        return max_step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=0\n",
    "        @cache\n",
    "        def di(i,j):\n",
    "            for x,y in (i-1,j+1),(i+1,j+1),(i,j+1):\n",
    "                if 0<=x<m and 0<=y<n and grid[x][y]>grid[i][j]:\n",
    "                    nonlocal ans\n",
    "                    ans=max(ans,y)\n",
    "                    di(x,y)\n",
    "        for i in range(m):\n",
    "            di(i,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        result = 0\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, col: int) -> int:\n",
    "            if col + 1 == m:\n",
    "                return col\n",
    "            \n",
    "            tmp = col\n",
    "            for i in [-1, 0, 1]:\n",
    "                # print(\"cur: \", row, col, grid[row][col])\n",
    "                # print(\"next: \", row + i, col + 1, grid[row + i][col + 1])\n",
    "                if row + i > -1 and row + i < n and grid[row + i][col + 1] > grid[row][col]:\n",
    "                    tmp = max(tmp, dfs(row + i, col + 1))\n",
    "            return tmp\n",
    "        \n",
    "        for i in range(n):\n",
    "            result = max(result, dfs(i, 0))\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        que = deque()\n",
    "        for i in range(m):\n",
    "            que.append((i, 0))\n",
    "\n",
    "        def pan(x, y):\n",
    "            if 0 <= x < m and 0 <= y < n: return True\n",
    "            return False\n",
    "\n",
    "        mp = defaultdict(int)\n",
    "        ans = 0\n",
    "        while len(que) > 0:\n",
    "            fro = que.popleft()\n",
    "            x = fro[0]\n",
    "            y = fro[1]\n",
    "            ans = max(mp[(x, y)], ans)\n",
    "            if pan(x - 1, y + 1) and grid[x - 1][y + 1] > grid[x][y] and mp[(x - 1, y + 1)] == 0:\n",
    "                que.append((x - 1, y + 1))\n",
    "                mp[(x - 1, y + 1)] = mp[(x, y)] + 1\n",
    "            if pan(x, y + 1) and grid[x][y + 1] > grid[x][y] and mp[(x, y + 1)] == 0:\n",
    "                que.append((x, y + 1))\n",
    "                mp[(x, y + 1)] = mp[(x, y)] + 1\n",
    "            if pan(x + 1, y + 1) and grid[x + 1][y + 1] > grid[x][y] and mp[(x + 1, y + 1)] == 0:\n",
    "                que.append((x + 1, y + 1))\n",
    "                mp[(x + 1, y + 1)] = mp[(x, y)] + 1\n",
    "        # print(que)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i,j) -> int:\n",
    "            if j == n -1 :\n",
    "                return 0 \n",
    "            res = 0\n",
    "            for k in i-1,i,i+1:\n",
    "                if 0<=k<m and grid[k][j+1] > grid[i][j]:\n",
    "                    res = max(res,dfs(k,j+1)+1)\n",
    "            return res \n",
    "        return max(dfs(i,0) for i in range(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxMoves(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            row0= (i==0)\n",
    "            rowm= (i==m-1)\n",
    "            coln = (j==n-1)\n",
    "            if coln:\n",
    "                return 0\n",
    "            if row0:\n",
    "                if grid[i][j]>=grid[i][j+1] and grid[i][j]>=grid[i+1][j+1]:\n",
    "                    return 0\n",
    "                elif grid[i][j]>=grid[i][j+1]:\n",
    "                    return dfs(i+1,j+1)+1\n",
    "                elif grid[i][j]>=grid[i+1][j+1]:\n",
    "                    return dfs(i,j+1)+1\n",
    "                else:\n",
    "                    return max(dfs(i,j+1),dfs(i+1,j+1))+1\n",
    "            if rowm:\n",
    "                if grid[i][j]>=grid[i][j+1] and grid[i][j]>=grid[i-1][j+1]:\n",
    "                    return 0\n",
    "                elif grid[i][j]>=grid[i][j+1]:\n",
    "                    return dfs(i-1,j+1)+1\n",
    "                elif grid[i][j]>=grid[i-1][j+1]:\n",
    "                    return dfs(i,j+1)+1\n",
    "                else:\n",
    "                    return max(dfs(i-1,j+1),dfs(i,j+1))+1\n",
    "            else:\n",
    "                if grid[i][j]>=grid[i][j+1] and grid[i][j]>=grid[i+1][j+1] and grid[i][j]>=grid[i-1][j+1]:\n",
    "                    return 0\n",
    "                elif grid[i][j]>=grid[i][j+1] and grid[i][j]>=grid[i+1][j+1]:\n",
    "                    return dfs(i-1,j+1)+1\n",
    "                elif grid[i][j]>=grid[i+1][j+1] and grid[i][j]>=grid[i-1][j+1]:\n",
    "                    return dfs(i,j+1)+1\n",
    "                elif grid[i][j]>=grid[i][j+1] and grid[i][j]>=grid[i-1][j+1]:\n",
    "                    return dfs(i+1,j+1)+1\n",
    "                elif grid[i][j]>=grid[i][j+1]:\n",
    "                    return max(dfs(i+1,j+1),dfs(i-1,j+1))+1\n",
    "                elif grid[i][j]>=grid[i-1][j+1]:\n",
    "                    return max(dfs(i+1,j+1),dfs(i,j+1))+1\n",
    "                elif grid[i][j]>=grid[i+1][j+1]:\n",
    "                    return max(dfs(i,j+1),dfs(i-1,j+1))+1\n",
    "                else:\n",
    "                    return max(dfs(i-1,j+1),dfs(i,j+1),dfs(i+1,j+1))+1\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            ans=max(ans,dfs(i,0))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
